时变单车路径问题建模及算法设计

doi:10.3969 /j.issn.1674-0696.2013.02.20

重庆交通大学学报（自然科学版） ›› 2013, Vol. 32 ›› Issue (2): 263-0266.DOI: 10.3969 /j.issn.1674-0696.2013.02.20

时变单车路径问题建模及算法设计

彭勇¹，谢禄江²，刘松¹

¹. 重庆交通大学交通运输学院，重庆400074; ². 永川供电局，重庆402160

出版日期:2013-04-15 发布日期:2018-01-26
作者简介:彭勇( 1973—) ，男，重庆人，副教授，博士，主要从事交通运输规划与管理方面的研究。
基金资助:
国家自然科学基金项目( 60974132) ; 重庆市教育委员会科学技术研究项目( KJ090415)

Route Modeling and Algorithm Designing of Time-Dependent Single Vehicle

Peng Yong¹，Xie Lujiang²，Liu Song¹

¹. School of Traffic ＆ Transportation，Chongqing Jiaotong University，Chongqing 400074，China;². Yongchuan Power Supply Bureau，Chongqing 402160，China

Online:2013-04-15 Published:2018-01-26

摘要/Abstract

摘要： 讨论了一类时变单车配送路径优化问题。综合考虑车辆行驶速度随时间、路段不同而变化的特点，及车辆为多条路线上的客户提供服务时对车辆路径优化的影响，建立了以配送完成时间最早为优化目标的时变单车配送路径优化模型。在行驶时间满足FIFO 规则下，设计了基于Inver-over 操作的PSO 启发式算法及满足贪婪配送策略下的动态规划精确求解算法，并讨论了增加贪婪补货策略的单车配送路径问题解与原问题解的关系。最后分别用两种算法对算例进行求解，并通过对求解优化结果及计算时间的对比分析验证了IOPSO 算法的有效性。

关键词: 路径优化, 动态规划, 粒子群算法, 时变, FIFO 规则

Abstract: The route optimization problems of one kind of time-dependent single vehicle are discussed. With the comprehensive consideration that vehicle’s velocity is changing with time and different sections of road，as well as the influence of vehicle route optimization when the vehicle provides service for multiple routes customers，a route optimization model of timedependent single vehicle is established，which takes the earliest distribution completion time as the optimization target. A particle swarm optimization algorithm based on inver-over operator with FIFO rule is developed. Adding greed dispatching restriction，a dynamic programming algorithm with FIFO rule is provided. The numerical example verifies the validity of theoretical analysis results.

Key words: route optimization, dynamic program, particle swarm optimization ( PSO) , time-dependent, FIFO rule

中图分类号:

U492.3 + 1

彭勇，谢禄江，刘松. 时变单车路径问题建模及算法设计[J]. 重庆交通大学学报（自然科学版）, 2013, 32(2): 263-0266.

Peng Yong，Xie Lujiang，Liu Song. Route Modeling and Algorithm Designing of Time-Dependent Single Vehicle[J]. Journal of Chongqing Jiaotong University(Natural Science), 2013, 32(2): 263-0266.

参考文献

［1］ Dantzig G，Ramser J. The truck dispatching problem ［J］. Management Science，1959，6: 80-91. ［2］ Taillard E D，Laporte G，Gendreau M. Vehicle routing with multiple use of vehicles［J］. Journal of the Operational Research Society，1996，47: 1065-1070. ［3］ Azi N，Gendreau M，Potvin J Y. An exact algorithm for a single vehicle routing problem with time windows and multiple routes ［J］.European Journal of Operational Research，2007，178: 755-766. ［4］彭勇. 变需求车辆路线问题建模及基于Inver-over 操作的PSODP算法［J］. 系统工程理论与实践， 2008，2 8( 10) : 76-81. Peng Yong. Research on vehicle routing problem with stochastic demand and PSO-DP algorithm with Inver-over operator ［J］. Systems Engineering Theory ＆ Practice，2008，28( 10) : 76-81. ［5］ Gribkovskaia I，Laporte G，Aliaksandr S. The single vehicle routing problem with deliveries and selective pickups ［J］. Computers and Operations Research，2008，35: 2908-2924. ［6］ Malandraki C，Daskin M S. Time dependent vehicle routing problems: formulations， properties and heuristic algorithms ［J］.Transportation Science，1992，26( 3) : 185-200. ［7］ Kok A L，Hans E W，Schutten J M J. Vehicle routing under timedependent travel times: the impact of congestion avoidance ［J］.Computers ＆ Operations Research，2012，39( 5) : 910-918. ［8］于青，赵辉. 基于GA 的时变路网中车辆动态派遣的研究［J］.计算机工程与应用，2008， 44( 22) : 210-212. Yu Qing，Zhao Hui. Research on time dependent vehicle routing problem based on GA ［J］. Computer Engineering and Applications，2008，44( 22) : 210-212. ［9］ Michalewicz Z，Fogel D B. How to Solve It: Modern Heuristics ［M］. Berlin: Springer-Verlag，2000. ［10］ Kennedy J，Eberhart R C. Particle Swarm Optimization［C］/ / Proceedings of IEEE International Conference on Neutral Networks.Australia: Perth Press，1995: 1942-1948. ［11］高海兵，周驰，高亮. 广义粒子群优化模型［J］. 计算机学报，2005，28( 12) : 1980-1987. Gao Haibing，Zhou Chi，Gao Liang. General particle swarm optimization model ［J］. Chinese Journal of Computers，2005，28( 12) :1980-1987.

[1]	史天亮，王文光. 信息观和粒子群算法在城市交通拥堵中的研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(04): 19-25.
[2]	李玉民，邱梦，闫凯丽，刘颀欣. 高铁参与下考虑时间窗的生鲜品多式联运路径选择[J]. 重庆交通大学学报（自然科学版）, 2021, 40(04): 54-61.
[3]	谢新连，刘超，魏照坤. 海洋气象环境影响下的复杂水域船舶路径规划[J]. 重庆交通大学学报（自然科学版）, 2021, 40(02): 1-7.
[4]	李楠，强懿耕，樊瑞. 基于轨迹压缩的航空器飞行轨迹聚类研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(01): 1-6.
[5]	隗寒冰,贺少川. 基于深度强化学习的插电式柴电混合动力汽车多目标优化控制策略[J]. 重庆交通大学学报（自然科学版）, 2021, 40(01): 44-52.
[6]	王莉莉，刘子昂. 针对平行航路的改航路径规划研究[J]. 重庆交通大学学报（自然科学版）, 2020, 39(08): 45-50.
[7]	张兆宁，王彤. 基于跑道出口滑行道选择的机场滑行路径优化[J]. 重庆交通大学学报（自然科学版）, 2020, 39(06): 33-39.
[8]	邬晓光1, 何启龙1, 2, 郑鹏1, 肖凯龙1. 基于支持向量机法的混凝土强度对拼宽T梁桥时变可靠度影响分析[J]. 重庆交通大学学报（自然科学版）, 2019, 38(05): 33-38.
[9]	于德新1，2，赵阳1，武毅1，瞿卫东1. 施工环境下高速公路应急车辆资源配置[J]. 重庆交通大学学报（自然科学版）, 2018, 37(10): 110-116.
[10]	陈辉国1，宋浩2，钟庭1，刘国粹1，王苗硕1. 基于Kameda模型的爆炸地震动时变功率谱拟合[J]. 重庆交通大学学报（自然科学版）, 2018, 37(08): 11-15.
[11]	刘帅1，唐伯明1，刘松2. 基于随机时变路网的运输路径选择[J]. 重庆交通大学学报（自然科学版）, 2017, 36(12): 110-114.
[12]	严南南，朱丽珊. 考虑碳交易的果蔬品供应链网络优化[J]. 重庆交通大学学报（自然科学版）, 2016, 35(6): 171-176.
[13]	李军，唐晓宇，赵长相. 基于充电策略的纯电动公交车辆调度优化[J]. 重庆交通大学学报（自然科学版）, 2015, 34(4): 107-112.
[14]	陈丹丹,洪卫,贾禹. 面向随机因素的多式联运动态路径优化[J]. 重庆交通大学学报（自然科学版）, 2015, 34(2): 112-117.
[15]	彭勇，何俊生. 实时路网单车多任务物流配送路径优化[J]. 重庆交通大学学报（自然科学版）, 2014, 33(2): 122-125.

时变单车路径问题建模及算法设计

Route Modeling and Algorithm Designing of Time-Dependent Single Vehicle

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics